﻿// 0907train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 编号0-3的处理器处于同一个链路中，编号4-7的处理器处于另外一个链路中，不同链路中的处理器不能通信。  
现给定服务器Q可用的处理器编号数组 array，以及任务申请的处理器数量 num，找出符合下列亲和性调度原则的芯片组合。  
如果不存在符合要求的组合，则返回空列表。

亲和性调度原则：  
如果申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳，其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个。  
如果申请处理器个数为2，则选择同一链路剩余可用的处理器数量2个的为最佳，其次是剩余4个，最后是剩余3个。  
如果申请处理器个数为4，则必须选择同一链路剩余可用的处理器数量为4个。  
如果申请处理器个数为8，则申请节点所有8个处理器。

提示：  
1. 任务申请的处理器数量只能是1、2、4、8。  
2. 编号0-3的处理器处于一个链路，编号4-7的处理器处于另外一个链路。  
3. 处理器编号唯一，且不存在相同编号处理器。

输入描述：  
输入包含可用的处理器编号数组 array，以及任务申请的处理器数量 num 两个部分。  
第一行为 array，第二行为 num。例如：  
[0, 1, 4, 5, 6, 7]  
1  
表示当前编号为0、1、4、5、6、7的处理器可用。任务申请1个处理器。  
0 <= array.length <= 8  
0 <= array[i] <= 7  
num ∈ [1, 2, 4, 8]

输出描述：  
输出为组合列表，当 array = [0, 1, 4, 5, 6, 7]，num = 1 时，输出为 [[0], [1]]。

示例1输入输出示例仅供调试，后台判题数据一般不包含示例  
输入：  
[0, 1, 4, 5, 6, 7]  
1  
输出：  
[[0], [1]]
 */
class Solution01
{
public:
    void backTrack(vector<int>&num_vec, int start)
    {
	    if (track.size()==sub_size_)
	    {
            result.push_back(track);
            return;
	    }

        for (int i=start; i<num_vec.size(); i++)
        {
	        //做选择
            track.push_back(num_vec[i]);
            //回溯
            backTrack(num_vec, i + 1);
            //撤销选择
            track.pop_back();
        }

        //backTrack
    }

    void getSubVec(vector<int>&num_vec)
    {
        backTrack(num_vec, 0);
    }

    Solution01(vector<int>&num_vec, int choose_count)
    {
        sub_size_ = choose_count;
        for (auto&num:num_vec)
        {
	        if (num<=3)
	        {
                processors_13.push_back(num);
	        }
            else
            {
                processors_47.push_back(num);
            }
        }

        int length13 = processors_13.size();
        int length47 = processors_47.size();

        //这里只写了一种情况，差不多就是这么个思路
        if (choose_count==1)
        {
            //申请处理器个数为1，则选择同一链路，剩余可用的处理器数量为1个的最佳
            if (length13==1||length47==1)
            {
	            if (length13==1)
	            {
                    getSubVec(processors_13);
	            }
                if (length47==1)
                {
                    getSubVec(processors_47);
                }
            }
            //其次是剩余3个的为次佳，然后是剩余2个，最后是剩余4个
            else if (length13 == 3 || length47 == 3)
            {
                if (length13 == 3)
                {
                    getSubVec(processors_13);
                }
                if (length47 == 3)
                {
                    getSubVec(processors_47);
                }
            }
            else if (length13 == 2 || length47 == 2)
            {
                if (length13 == 2)
                {
                    getSubVec(processors_13);
                }
                if (length47 == 2)
                {
                    getSubVec(processors_47);
                }
            }
            else if (length13 == 4 || length47 == 4)
            {
                if (length13 == 4)
                {
                    getSubVec(processors_13);
                }
                if (length47 == 4)
                {
                    getSubVec(processors_47);
                }
            }

        }

        //打印result
        cout << '[';
        for (int vec_i=0; vec_i<result.size(); vec_i++)
        {
            vector<int>min_result = result[vec_i];
            cout << '[';
            for (int i=0; i<min_result.size(); i++)
            {
                cout << min_result[i];
                if (i!= min_result.size()-1)
                {
                    cout << ',';
                }
            }
            cout << ']';

            if (vec_i!=result.size()-1)
            {
                cout << ',';
            }
        }
        cout << ']';
        //Solution01
    }
private:
    vector<int> processors_13, processors_47;
    vector<vector<int>>result;
    vector<int>track;
    int sub_size_ = 0;
};


/*
 题目：  
小明在做构造数列的题目，题目要求数列中第一个数为n，
且数列后面的每一个数字都不能大于前一个数字的一半，数列的元素都是正整数，
请问在给定n的情况下，最多能构造多少合法且不同的数列？
 3<=7/2 j*2<=i

输入描述：  
输入一个n  
备注：1 <= n < 10000

输出描述：  
输出可以构造的序列个数

示例1：  
输入：  
7  
输出：  
6  
说明：  
可以构成 [7], [7,3], [7,2], [7,1], [7,3,1], [7,2,1]

示例2：  
输入：  
5  
输出：  
4  
说明：  
可以构成 [5], [5,2], [5,1], [5,2,1]
 */
class Solution02
{
public:
    Solution02(int num)
    {
        if (num==1)
        {
            cout << 1;
            return;
        }

        vector<int>dynamic_vec(num + 1, 1);
        dynamic_vec[0] = 0;

        //j*2<=i
        //倒数第二个数j，j*2<=i
        for (int i=2; i<=num; i++)
        {
	        for (int j=1; j*2<=i; j++)
	        {
                dynamic_vec[i] += dynamic_vec[j];
	        }
        }

        cout << dynamic_vec[num];

        //Solution02
    }
};


/*
 静态扫描可以快速识别源代码的缺陷，静态扫描的结果以扫描报告作为输出：
1. 文件扫描的成本和文件大小相关，如果文件大小为N，则扫描成本为N个金币
2. 扫描报告的缓存成本和文件大小无关，每缓存一个报告需要M个金币
3. 扫描报告缓存后，后继再碰到该文件则不需要扫描成本，直接获取缓存结果
给出源代码文件标识序列和文件大小序列，求解采用合理的缓存策略，最少需要的金币数

输入描述
第一行为缓存一个报告金币数M，1 <= M <= 100
第二行为文件标识序列：F1,F2,F3,…,Fn
第三行为文件大小序列：S1,S2,S3,…,Sn

- 1 <= N <= 10000
- 1 <= Fi <= 1000
- 1 <= Si <= 10

输出描述
采用合理的缓存策略，需要的最少金币数

输入
5
1 2 2 1 2 3 4
1 1 1 1 1 1 1
输出
7

文件大小相同，扫描成本均为1个金币。缓存任意文件均不合算，因而最少成本为7金币

输入
5
2 2 2 2 2 5 2 2 2
3 3 3 3 3 1 3 3 3
输出
9
3（扫描2）+5（缓存2）+1（扫描5）
 */
class Solution03
{
public:
    unordered_map<int, int>single_map;
    unordered_map<int, int>sum_map;
    unordered_map<int, int>result_map;
    Solution03(vector<vector<int>>&num_vec, int combine_price)
    {
	    //0 index 1price
        //思考，什么时候应该缓存？单个文件的大小，超过limit_price+single_price缓存
        //建2个表，一个存总和，一个存单份扫描的价格
        for (auto&min_vec:num_vec)
        {
            int index = min_vec[0];
            int price = min_vec[1];

            single_map[index] = price;
            sum_map[index] += price;
        }

        for (auto&map_item:single_map)
        {
            int index = map_item.first;
            int sum_price = sum_map[index];
            int single_price = map_item.second;

            //总和>单次扫描+缓存
            if (sum_price>single_price+ combine_price)
            {
                result_map[index] = single_price + combine_price;
            }
            else
            {
                result_map[index] = sum_price;
            }

        }

        int result = 0;
        for (auto&map_item:result_map)
        {
            result += map_item.second;
        }
        cout << result;
        //Solution03
    }
};


int main()
{
	{
        int combine_price;
        cin >> combine_price;
        cin.ignore();

        vector<int>index_vec;
        vector<int>price_vec;

        string input;
        getline(cin, input);
        stringstream index_sstream(input);
        string token;
        while (index_sstream >>token)
        {
            index_vec.push_back(stoi(token));
        }

        getline(cin, input);
        stringstream price_sstream(input);
        while (price_sstream>>token)
        {
            price_vec.push_back(stoi(token));
        }

        vector<vector<int>>num_vec;
        for (int i=0; i<index_vec.size(); i++)
        {
            vector<int>min_vec(2);
            min_vec[0] = index_vec[i];
            min_vec[1] = price_vec[i];
            num_vec.push_back(min_vec);
        }

        Solution03 solu(num_vec, combine_price);

        return 0;
	}
	{
        int num = 5;
        Solution02 solu(num);

        return 0;
	}
    vector<int>num_vec = { 0, 1, 4, 5, 6, 7 };
    int choose_count = 1;
    Solution01 solu(num_vec, choose_count);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
